package q377_combinationSum4;

public class Solution_1 {
    /**
     * 此题要和518题对照看 同样是背包问题 但是这次的背包问题是求解所有的排列！
     * 乍一看我们可以采用和518题一样的方法，但是求解所有的排列时我们需要将背包和物品的循环进行更改
     * 题中说到：顺序不同的序列被视作不同的组合
     * 这也就是实际上求排列的意思
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];

        dp[0] = 1;

        // 我们可以对照518题的代码 几乎一模一样的代码 但循环的内外发生了变化
//        for (int num : nums) { // 遍历所有我们能用的硬币
//            for (int j = num; j <= target; j++) { // 遍历我们dp的容量 完全背包是采用正序遍历的
//                // 组合数的递推公式
//                dp[j] = dp[j] + dp[j - num]; // 当前的dp[j] = 当前的dp[j] + 当前的dp[j - nums[i]]
//            }
//        }

        for (int i = 0; i <= target; i++) { // 先遍历所有的背包容量
            for (int j = 0; j < nums.length; j++) { // 然后再按次序遍历我们的物品

                // 需要考虑的是 为什么我们不将该条件写在循环的判断语句中？
                // 因为循环发现nums[j] > i时 会直接结束循环 但后面的num[j]并不一定无法参与计算
                if (nums[j] <= i){
                    dp[i] = dp[i] + dp[i - nums[j]];
                }
            }
        }

        return dp[target];

    }
}
